package com.mc.graph;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

/**
 * 有向图中基于深度优先搜索的顶点排序
 * 不同的顶点排序只是在访问顶点时，顶点记录顺序的不同
 * @author MC
 *
 */
public class DepthFirstOrder {
	private boolean marked[];
	private Queue<Integer> pre;//先序队列
	private Queue<Integer> post;//后续队列
	private Stack<Integer> reversePost;//逆后续
	
	public DepthFirstOrder(Digraph G){
		pre = new ArrayDeque<Integer>();
		post = new ArrayDeque<Integer>();
		reversePost = new Stack<Integer>();
		marked = new boolean[G.V()];
		for(int v=0;v<G.V();v++){
			if(!marked[v])dfs(G,v);
		}
	}
	
	private void dfs(Digraph G,int v){
		marked[v] = true;
		pre.add(v);
		for(int w:G.adj(v)){
			if(!marked[w])
				dfs(G,w);
		}
		post.add(v);
		reversePost.push(v);
	}
	
	public Iterable<Integer> pre(){
		return pre;
	}
	public Iterable<Integer> post(){
		return post;
	}
	public Iterable<Integer> reversePost(){
		return reversePost;
	}
}
